//等式方程的可满足性
//https://leetcode.cn/problems/satisfiability-of-equality-equations/

class Solution {
public:
    vector<int> arr;

    Solution() : arr(300, 0) {
        for (int i = 0; i < arr.size(); i++) {
            arr[i] = i;
        }
    }

    int findfather(int pos) {
        if (arr[pos] == pos)
            return pos;
        return arr[pos] = findfather(arr[pos]);
    }

    bool equationsPossible(vector<string>& equations) {        
        int n = equations.size();
        for (int i = 0; i < n; i++) 
        {       
            if (equations[i][1] == '=') 
            {
                int c1 = findfather(equations[i][0]);
                int c2 = findfather(equations[i][3]);
                if (c1 != c2) arr[c1] = c2;           
            }  
        }

        for (int i = 0; i < n; i++) 
        {
            int c1 = findfather(equations[i][0]);
            int c2 = findfather(equations[i][3]);
            if (equations[i][1] == '!') 
            {
                if(c1 == c2) return false;
            }  
        }

        return true;
    }
};